// @algorithm @lc id=813 lang=cpp 
// @title all-paths-from-source-to-target


// @test([[1,2],[3],[3],[]])=[[0,1,3],[0,2,3]]
// @test([[4,3,1],[3,2,4],[3],[4],[]])=[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
// @test([[1],[]])=[[0,1]]
// @test([[1,2,3],[2],[3],[]])=[[0,1,2,3],[0,2,3],[0,3]]
// @test([[1,3],[2],[3],[]])=[[0,1,2,3],[0,3]]
class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ans;
        auto n = graph.size();
        vector<int> path(1,0);
        function<void(int)> dfs = [&](int i){
            if(i==n-1){
                ans.push_back(path);
                return;
            }
            for(auto & j : graph[i]){
                path.push_back(j);
                dfs(j);
                path.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};